Tutorial 1 1
El viernes 4 de abril (el cumpleaños de mi papá, btw ·o·) fue el examen de INF-111... No tengo el examen ·n· pero recuerdo la primera pregunta ·u· Antes de comenzar, debería advertir que este tutorial está enfocado a alumnos de INF-111, así que hablaré despacio XD Descripción del problema Tenemos un lote de números, y queremos rotar el último dígito de cada número hacia la izquierda, de tal forma que: el último dígito del 1er número quede en el último dígito del último número, y el último dígito del 2do número, quede en el último dígito del 1ro... Supongamos que el lote está compuesto de n números, y los números del lote son: a1, a2, a3, ... , an Entonces, lo que queremos hacer, es mostrar un nuevo lote de números, compuesto por: b1, b2, b3, ... , bn, de tal forma que, en general, se cumplan las siguientes dos reglas: 1ra regla: el último dígito de bi es el último dígito de ai+1 (para i distinto de n). 2da regla: el último dígito de bn es el último dígito de a1 Datos de entrada Se te dará un número n seguido de n números que componen un lote. Datos de salida Debes imprimir un lote de n números que cumpla las 2 reglas expuestas en la descripción del problema. Ejemplo INPUT 3 123 456 789 OUTPUT 423 756 189 Solución Creo que con esta imagen se entenderá mejor el problema: thumb Veamos el Input: si movemos los números resaltados, de acuerdo a las flechitas, obtenemos el output. Veamos el Output: si movemos los números resaltados, de acuerdo a las flechitas, obtendremos el input. Antes de comenzar a resolver el problema, hay algunas curiosidades que deberían haber llamado tu atención sobre el problema (son aspectos clave para solucionarlo): Debemos guardarnos en algún lugar el último dígito del 1er número, porque vamos a necesitarlo para construir al último número que vamos a imprimir. Cada vez que leamos un número nuevo en el lote, necesitamos guardar en algún lugar el número anterior, porque vamos a necesitar el último dígito del número "actual", para construir al "número anterior". Ahora sí... let's solve this shit! Vamos a "recordar" al último dígito del primer número. Además, cada vez que leamos un nuevo número del lote, necesitaremos "recordar" cuál es el anterior. Pero recuerda que la computadora no puede recordar nada, a menos que tú le pidas que lo recuerde! pero... ¿cómo le pedimos a una computadora que recuerde algo? bueno, las variables pueden ayudarnos.... entonces, necesitaremos una variable por cada dato que vamos a "recordar". Por ahora, definiremos 2 variables: digitoPrimerNumero en donde guardaremos el último dígito del primer número del lote. anterior en donde guardaremos el número que está antes del número del lote con el que estamos trabajando actualmente. el valor de la variable digitoPrimerNumero será asignado cuando leamos el primer número del lote, después, no lo vamos a modificar (ni usar), hasta que tengamos al último número del lote. Cuando esto suceda, necesitaremos poner este dígito, en el último dígito del número. Nuestro pseudocódigo, va quedando así: Leer en "n" la cantidad de números que tiene el lote. Leer en "anterior" el primer número del lote. Extraer el último dígito de "anterior" y ponerlo en "digitoPrimerNumero". ... Ahora, necesitamos continuar leyendo el resto de números del lote. Como ya hemos leído uno de los números del lote, nos quedan por leer n-1 números. Y esto es lo que haremos cada vez que leamos un número nuevo: Leemos el número, y lo guardamos en una variable llamda "actual". Luego, necesitamos extraer el último dígito de este número, para ponérselo al número "anterior", por último, el número "actual" pasaría a ser el "anterior", porque estamos por leer un número nuevo, y este número nuevo que vamos a leer es ahora el "actual", y el proceso se repite hasta llegar al último número. El pseudocódigo continúa de esta manera: ... Repetir n-1 veces: leer en "actual" un número del lote. extraer el último dígito del número "actual", y guardarlo en "digitoNumeroActual". poner el "digitoNumeroActual" como el último dígito del número "anterior". mostrar al número "anterior". "anterior" = "actual" (el número actual se transforma en el número anterior). ... Cuando este ciclo se termine, habremos mostrado n-1 números del lote-respuesta. ¿Por qué? bueno, el último número del lote respuesta estará en la variable "anterior", y como el ciclo se rompió, no se va a mostrar (dentro del ciclo). Así que, lo que tenemos que hacer para mostrar al último número de la respuesta es: poner el último dígito del primer número del lote1, en el último dígito del último número de la respuesta2. 1: el último dígito del primer número del lote lo tenemos guardado en la variable "digitoPrimerNumero", y lo obtuvimos en el primer trozo de pseudocódigo del tutorial 2: el último número de la respuesta, está en la variable "anterior" al terminar el ciclo de la 2da porción de pseudocódigo de este tutorial. Por el momento, la variable "anterior" tiene el último número del lote, luego de quitarle el último dígito Nuestro pseudocódigo va quedando así: ... poner en el último dígito de "anterior" el "digitoPrimerNumero". mostrar el número "anterior". fin! :) Bueno, eso es todo... aquí está el pseudocódigo completo: 1. Leer en "n" la cantidad de números que tiene el lote. 2. Leer en "anterior" el primer número del lote. 3. Extraer el último dígito de "anterior" y ponerlo en "digitoPrimerNumero". 4. Repetir n-1 veces: 5. leer en "actual" un número del lote. 6. extraer el último dígito del número "actual", y guardarlo en "digitoNumeroActual". 7. poner el "digitoNumeroActual" como el último dígito del número "anterior". 8. mostrar al número "anterior". 9. "anterior" = "actual" (el número actual se transforma en el número anterior). 10. poner en el último dígito de "anterior" el "digitoPrimerNumero". 11. mostrar el número "anterior". fin! :) Si analizamos el pseudocódigo, podemos extraer partes que "parecen" complicadas, y digerirlas en fórmulas matemáticas, o porciones de código más "claras". Eso de "extraer", en la 3ra línea, suena un poco complicado, cierto? no es tan complicado ;) vamos a analizarlo! Para extraer el último dígito de un número: Si queremos obtener el último dígito del número 165, lo dividimos entre 100=102, y al resultado le sacamos la parte entera. Si queremos obtener el último dígito del número 5,796,383, lo dividimos entre 10000000 = 106, y al resultado le sacamos la parte entera. En general, si quieremos obtener el último dígito de un número n, lo dividimos entre 10cantidadDeDigitosDeN - 1. Bueno, ya sabemos cuál era el último dígito del número n, pero aún no lo hemos "extraído". Para extraerlo, necesitamos quitarlo del número, y lo haremos así: ultimoDigito = n/10log10(n) n = n - ultimoDigito*10log10(n) Bueno, creo que esa era la única parte confusa del pseudocódigo... y ahora sí, en un código un poco más "digerido", la solución se verá algo así: leer(n) si n>0 leer(anterior) digitoPrimerNumero = parteEntera(anterior / (10 ^ (parteEntera(log10(anterior))))) anterior -= digitoPrimerNumero * 10 ^ parteEntera(log10(anterior)) de lo contrario, no hacer nada :P for( i=1 to i < n-1 ) leer(actual) digitoNumeroActual = parteEntera(actual / (10 ^ parteEntera(log10(actual)))) actual -= digitoNumeroActual * 10 ^ parteEntera(log10(actual)) anterior += digitoNumeroActual * 10 ^ parteEntera(log10(anterior)+1) mostrar(anterior) anterior = actual anterior += digitoPrimerNumero * 10 ^ parteEntera(log10(anterior)+1) mostrar(anterior) fin :) y he aquí el código en C++ int main(){ int n; cin >> n; int firstJump, prev, current, currentJump; if(n>0) { cin >> prev; firstJump = prev/(pow(10, (int) log10(prev))); prev -= firstJump * pow(10, (int) log10(prev)); n--; } while(n--) { cin >> current; currentJump = current/pow(10, (int) log10(current)); current -= currentJump * pow(10, (int) log10(current)); prev += currentJump * pow(10, (int) log10(prev)+1); cout << prev << " "; prev = current; } prev += firstJump * pow(10, (int) log10(prev)+1); cout << prev << endl; } that's it folks! Aclaraciones para entender C++: 1: En c++, un 'false' es igual que un 0, y cualquier número distinto de 0, es un 'true'. por eso, while(n--) hará lo siguiente: 1ro: verificará si n es 0. Si n es 0 sería como decir "while(false)" y el ciclo se romperá, si n es distinto de 0, sería como decir "while(true)" y el ciclo seguirá corriendo. 2do: le restará 1 a n.